package puzzle.projecteuler.p100;

import java.util.Arrays;

import astudy.util.AdvMath;

public class Problem046 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int max = 10000;
		Integer[] ps = AdvMath.primes(max);
		for (int i = 3; i < max; i ++) {
			if (i%2 == 1 && Arrays.binarySearch(ps, i) < 0 && !check(i, ps)) {
				System.out.println(i);
				break;
			} else {
				continue;
			}
		}
	}
	
	private static boolean check(int n, Integer[] ps) {
		for (int j = 1; j < ps.length && ps[j] < n; j ++) {
			int d = (n-ps[j])/2;
			int t = (int)Math.sqrt(d);
			if (t*t == d) {
				return true;
			}
		}
		return false;
	}
}
